//给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [2,2,3,2]
//输出：3
// 
//
// 示例 2： 
//
// 
//输入：nums = [0,1,0,1,0,1,99]
//输出：99
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 3 * 104 
// -231 <= nums[i] <= 231 - 1 
// nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 
// 
//
// 
//
// 进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？ 
// Related Topics 位运算 
// 👍 667 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

/**
 * Java：只出现一次的数字 II
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P137_SingleNumberIi {
    public static void main(String[] args) {
        Solution solution = new P137_SingleNumberIi().new Solution();
        int[] array = MyUtil.createArray(0, 1, 0, 1, 0, 1, 88);
        MyUtil.print(solution.singleNumber(array));

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int singleNumber(int[] nums) {
            if (nums.length == 1) {
                return nums[0];
            }
            // 按位累加和数组
            int[] sum = new int[32];
            for (int i = 0; i < nums.length; i++) {
                for (int j = 0; j < 32; j++) {
                    if (((nums[i] >> j) & 1) != 0) {
                        sum[j]++;
                    }
                }
            }
            // 不能被3除尽的表示有1
            int ans = 0;
            for (int i = 0; i < 32; i++) {
                if (sum[i] % 3 != 0) {
                    ans |= (1 << i);
                }
            }
            return ans;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}